package org.example.l2;

import org.junit.jupiter.api.Test;

import java.util.*;

public class Tree {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> re = new ArrayList<>();
        inorder(root, re);
        return re;
    }

    void inorder(TreeNode node,
                 List<Integer> res) {
        if (node == null) {
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    public int maxDepthV2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int max = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size != 0; size--) {
                TreeNode node = queue.poll();
                Optional.ofNullable(node.left).ifPresent(queue::offer);
                Optional.ofNullable(node.right).ifPresent(queue::offer);
            }
            max++;
        }

        return max;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }

    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }

    boolean isSymmetric(TreeNode l,
                        TreeNode r) {
        if (l == null && r == null) {
            return true;
        }
        if (l == null || r == null) {
            return false;
        }

        return l.val == r.val && isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
    }

    int diameterOfBinaryTreeRes = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dep(root);
        return diameterOfBinaryTreeRes;
    }

    int dep(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int l = dep(node.left);
        int r = dep(node.right);
        diameterOfBinaryTreeRes = Math.max(diameterOfBinaryTreeRes, l + r);
        return Math.max(l, r) + 1;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> res = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> sub = new ArrayList<>();
            for (int size = queue.size(); size > 0; size--) {
                TreeNode node = queue.poll();
                sub.add(node.val);
                Optional.ofNullable(node.left).ifPresent(queue::offer);
                Optional.ofNullable(node.right).ifPresent(queue::offer);
            }

            res.add(sub);
        }

        return res;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    TreeNode sortedArrayToBST(int[] nums,
                              int l,
                              int r) {
        if (l > r) {
            return null;
        }

        int mid = (l + r) >> 1;
        TreeNode left = sortedArrayToBST(nums, l, mid - 1);
        TreeNode right = sortedArrayToBST(nums, mid + 1, r);
        return new TreeNode(nums[mid], left, right);
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    boolean isValidBST(TreeNode node,
                       long down,
                       long up) {
        if (node == null) {
            return true;
        }

        int val = node.val;
        if (val <= down || val >= up) {
            return false;
        }

        return isValidBST(node.left, down, val) && isValidBST(node.right, val, up);
    }

    class KthSmallest {
        int res;
        int k;
    }

    public int kthSmallest(TreeNode root,
                           int k) {
        KthSmallest res = new KthSmallest();
        res.k = k;
        kthSmallestHelper(root, res);
        return res.res;
    }

    void kthSmallestHelper(TreeNode root,
                           KthSmallest res) {

        if (root == null) {
            return;
        }

        kthSmallestHelper(root.left, res);
        res.k--;
        if (res.k == 0) {
            res.res = root.val;
            return;
        }

        kthSmallestHelper(root.right, res);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (res == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for (int size = queue.size(); size != 0; size--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                Optional.ofNullable(node.left).ifPresent(queue::offer);
                Optional.ofNullable(node.right).ifPresent(queue::offer);
            }
            res.add(list.get(list.size() - 1));
        }

        return res;
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        flatten(root.right);
        flatten(root.left);

        TreeNode left = root.left;
        if (left != null) {
            TreeNode node = left;
            if (node != null) {
                while (node.right != null) {
                    node = node.right;
                }
                node.right = root.right;
            }
            root.right = left;
            root.left = null;
        }
    }

    public int pathSum(TreeNode root,
                       int targetSum) {
        if (root == null) {
            return 0;
        }

        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    int rootSum(TreeNode node,
                long targetSum) {
        if (node == null) {
            return 0;
        }

        int res = 0;
        int v = node.val;
        if (v == targetSum) {
            res++;
        }

        res += rootSum(node.left, targetSum - v);
        res += rootSum(node.right, targetSum - v);
        return res;
    }

    @Test
    void lowestCommonAncestor() {
        TreeNode build = TreeNode.build("[3,5,1,6,2,0,8,null,null,7,4]");
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(1);
        TreeNode treeNode = lowestCommonAncestor(build, p, q);
        System.out.println(treeNode.val);

    }

    public TreeNode lowestCommonAncestor(TreeNode root,
                                         TreeNode p,
                                         TreeNode q) {
        if (root == null) {
            return null;
        }

        lowestCommonAncestor2(root, p, q);
        return res;
    }

    TreeNode res;
    boolean lowestCommonAncestor2(TreeNode node,
                                  TreeNode n1,
                                  TreeNode n2) {
        if (node == null) {
            return false;
        }

        boolean l = lowestCommonAncestor2(node.left, n1, n2);
        boolean r = lowestCommonAncestor2(node.right, n1, n2);

        boolean eq = node.val == n1.val || node.val == n2.val;
        if ((l && r) || (eq && (l || r))) {
            res = node;
        }

        return l || r || eq;
    }


    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        maxGain(root);
        return maxSum;
    }

    int maxSum = Integer.MIN_VALUE;
    int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int l = maxGain(node.left);
        int r = maxGain(node.right);
        l = Math.max(l, 0);
        r = Math.max(r, 0);
        int t = l + r + node.val;
        maxSum = Math.max(maxSum, t);
        return node.val + Math.max(l, r);
    }
}